package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/most-frequent-subtree-sum">出现次数最多的子树元素和(Most Frequent Subtree Sum)</a>
 * <p>给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。</p>
 * <p>一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入: root = [5,2,-3]
 *              5
 *             / \
 *            2  -3
 *      输出: [2,-3,4]
 *
 * 示例 2：
 *      输入: root = [5,2,-5]
 *              5
 *             / \
 *            2  -5
 *      输出: [2]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>节点数在 [1, 10^4] 范围内</li>
 *     <li>-10^5 <= Node.val <= 10^5</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/22 17:35
 */
public class LC0508FindFrequentTreeSum_M {
    static class Solution {
        Map<Integer, Integer> cnt = new HashMap<>();
        int maxCnt = 0;

        public int[] findFrequentTreeSum(TreeNode root) {
            dfs(root);
            List<Integer> resList = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                if (entry.getValue() == maxCnt) {
                    resList.add(entry.getKey());
                }
            }
            int[] ans = new int[resList.size()];
            for (int i = 0; i < resList.size(); i++) {
                ans[i] = resList.get(i);
            }
            return ans;
        }

        private int dfs(TreeNode currNode) {
            if (currNode == null) {
                return 0;
            }
            int sum = currNode.val + dfs(currNode.left) + dfs(currNode.right);
            cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            maxCnt = Math.max(maxCnt, cnt.get(sum));
            return sum;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.findFrequentTreeSum(Generator.buildTree(5, 2, -3)));
        Printer.printArrayInt(solution.findFrequentTreeSum(Generator.buildTree(5, 2, -5)));
    }
}